SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Semaphore (programming)</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Semaphore (programming)</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about the computer programming term. For other uses, see <a href="Semaphore_(disambiguation)" class="mw-disambig" title="Semaphore (disambiguation)">Semaphore (disambiguation)</a>.</div>

<p>In <a href="Computer_science" title="Computer science">computer science</a>, a <b>semaphore</b> is a <a href="Variable_(programming)" class="mw-redirect" title="Variable (programming)">variable</a> or <a href="Abstract_data_type" title="Abstract data type">abstract data type</a> used to control access to a common resource by multiple <a href="Process_(computing)" title="Process (computing)">threads</a> and avoid <a href="Critical_section" title="Critical section">critical section</a> problems in a <a href="Concurrent_computing" title="Concurrent computing">concurrent</a> system such as a <a href="Computer_multitasking" title="Computer multitasking">multitasking</a> operating system. Semaphores are a type of <a href="Synchronization_(computer_science)" title="Synchronization (computer science)">synchronization primitive</a>. A trivial semaphore is a plain variable that is changed (for example, incremented or decremented, or toggled) depending on programmer-defined conditions.

</p><p>A useful way to think of a semaphore as used in a real-world system is as a record of how many units of a particular resource are available, coupled with operations to adjust that record <i>safely</i> (i.e., to avoid <a href="Race_condition" title="Race condition">race conditions</a>) as units are acquired or become free, and, if necessary, wait until a unit of the resource becomes available.

</p><p>Though semaphores are useful for preventing race conditions, they do not guarantee their absence. Semaphores that allow an arbitrary resource count are called <b>counting semaphores</b>, while semaphores that are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available) are called <b>binary semaphores</b> and are used to implement <a href="Lock_(computer_science)" title="Lock (computer science)">locks</a>.

</p><p>The semaphore concept was invented by <a href="Dutch_people" title="Dutch people">Dutch</a> <a href="Computer_scientist" title="Computer scientist">computer scientist</a> <a href="Edsger_Dijkstra" class="mw-redirect" title="Edsger Dijkstra">Edsger Dijkstra</a> in 1962 or 1963,<sup id="cite_ref-ReferenceA_1-0" class="reference"><a href="#cite_note-ReferenceA-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> when Dijkstra and his team were developing an <a href="Operating_system" title="Operating system">operating system</a> for the <a href="Electrologica_X8" title="Electrologica X8">Electrologica X8</a>. That system eventually became known as the <a href="THE_multiprogramming_system" title="THE multiprogramming system">THE multiprogramming system</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Library_analogy">Library analogy</h2></div>

<p>Suppose a physical <a href="Library" title="Library">library</a> has ten identical study rooms, to be used by one student at a time. Students must request a room from the front desk. If no rooms are free, students wait at the desk until someone relinquishes a room. When a student has finished using a room, the student must return to the desk and indicate that the room is free.

</p><p>In the simplest implementation, the <a href="Clerk" title="Clerk">clerk</a> at the <a href="Receptionist" title="Receptionist">front desk</a> knows only the number of free rooms available. This requires that all of the students use their room while they have signed up for it and return it when they are done. When a student requests a room, the clerk decreases this number. When a student releases a room, the clerk increases this number. The room can be used for as long as desired, and so it is not possible to book rooms ahead of time.

</p><p>In this scenario, the front desk count-holder represents a counting semaphore, the rooms are the resource, and the students represent processes/threads. The value of the semaphore in this scenario is initially 10, with all rooms empty. When a student requests a room, they are granted access, and the value of the semaphore is changed to 9. After the next student comes, it drops to 8, then 7, and so on. If someone requests a room and the current value of the semaphore is 0,<sup id="cite_ref-LittleBookOfSemaphores_2-0" class="reference"><a href="#cite_note-LittleBookOfSemaphores-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> they are forced to wait until a room is freed (when the count is increased from 0). If one of the rooms was released, but there are several students waiting, then any method can be used to select the one who will occupy the room (like <a href="FIFO_(computing_and_electronics)" title="FIFO (computing and electronics)">FIFO</a> or randomly picking one). And of course, a student must inform the clerk about releasing their room only after really leaving it.

</p>

<div class="mw-heading mw-heading3"><h3 id="Important_observations">Important observations</h3></div>

<p>When used to control access to a <a href="Pool_(computer_science)" title="Pool (computer science)">pool</a> of resources, a semaphore tracks only <i>how many</i> resources are free. It does not keep track of <i>which</i> of the resources are free. Some other mechanism (possibly involving more semaphores) may be required to select a particular free resource.

</p><p>The paradigm is especially powerful because the semaphore count may serve as a useful trigger for a number of different actions. The librarian above may turn the lights off in the study hall when there are no students remaining, or may place a sign that says the rooms are very busy when most of the rooms are occupied.

</p><p>The success of the protocol requires applications to follow it correctly. Fairness and safety are likely to be compromised (which practically means a program may behave slowly, act erratically, <a href="Hang_(computing)" title="Hang (computing)">hang</a>, or <a href="Crash_(computing)" title="Crash (computing)">crash</a>) if even a single process acts incorrectly. This includes:

</p>

<ul><li>requesting a resource and forgetting to release it;</li>

<li>releasing a resource that was never requested;</li>

<li>holding a resource for a long time without needing it;</li>

<li>using a resource without requesting it first (or after releasing it).</li></ul>

<p>Even if all processes follow these rules, <i>multi-resource <a href="Deadlock_(computer_science)" title="Deadlock (computer science)">deadlock</a></i> may still occur when there are different resources managed by different semaphores and when processes need to use more than one resource at a time, as illustrated by the <a href="Dining_philosophers_problem" title="Dining philosophers problem">dining philosophers problem</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Semantics_and_implementation">Semantics and implementation</h2></div>

<p>Counting semaphores are equipped with two operations, historically denoted as P and V (see <a href="#Operation_names">§ Operation names</a> for alternative names). Operation V increments the semaphore <i>S</i>, and operation P decrements it.

</p><p>The value of the semaphore <i>S</i> is the number of units of the resource that are currently available. The P operation <a href="Busy_waiting" title="Busy waiting">wastes time</a> or <a href="Sleep_(system_call)" title="Sleep (system call)">sleeps</a> until a resource protected by the semaphore becomes available, at which time the resource is immediately claimed. The V operation is the inverse: it makes a resource available again after the process has finished using it.

One important property of semaphore <i>S</i> is that its value cannot be changed except by using the V and P operations.

</p><p>A simple way to understand <style data-mw-deduplicate="TemplateStyles:r886049734">

/* start https://en.wikipedia.org/ */

.mw-parser-output .monospaced{font-family:monospace,monospace}

/* end https://en.wikipedia.org/ */

</style><span class="monospaced">wait</span> (P) and <span class="monospaced">signal</span> (V) operations is:

</p>

<ul><li><span class="monospaced">wait</span>: Decrements the value of the semaphore variable by 1. If the new value of the semaphore variable is negative, the process executing <span class="monospaced">wait</span> is blocked (i.e., added to the semaphore's queue). Otherwise, the process continues execution, having used a unit of the resource.</li>

<li><span class="monospaced">signal</span>: Increments the value of the semaphore variable by 1. After the increment, if the pre-increment value was negative (meaning there are processes waiting for a resource), it transfers a blocked process from the semaphore's waiting queue to the ready queue.</li></ul>

<p>Many operating systems provide efficient semaphore primitives that unblock a waiting process when the semaphore is incremented. This means that processes do not waste time checking the semaphore value unnecessarily.

</p><p>The counting semaphore concept can be extended with the ability to claim or return more than one "unit" from the semaphore, a technique implemented in <a href="Unix" title="Unix">Unix</a>. The modified V and P operations are as follows, using square brackets to indicate <a href="Atomic_operation" class="mw-redirect" title="Atomic operation">atomic operations</a>, i.e., operations that appear indivisible to other processes:

</p>

<pre><b>function</b> V(semaphore S, integer I):

[S ← S + I]

<b>function</b> P(semaphore S, integer I):

<b>repeat:</b>

[<b>if</b> S ≥ I:

S ← S − I

<b>break</b>]

</pre>

<p>However, the rest of this section refers to semaphores with unary V and P operations, unless otherwise specified.

</p><p>To avoid <a href="Resource_starvation" class="mw-redirect" title="Resource starvation">starvation</a>, a semaphore has an associated <a href="Queue_(data_structure)" class="mw-redirect" title="Queue (data structure)">queue</a> of processes (usually with <a href="FIFO_(computing_and_electronics)" title="FIFO (computing and electronics)">FIFO</a> semantics). If a process performs a P operation on a semaphore that has the value zero, the process is added to the semaphore's queue and its execution is suspended. When another process increments the semaphore by performing a V operation, and there are processes on the queue, one of them is removed from the queue and resumes execution. When processes have different priorities the queue may be ordered thereby, such that the highest priority process is taken from the queue first.

</p><p>If the implementation does not ensure atomicity of the increment, decrement, and comparison operations, there is a risk of increments or decrements being forgotten, or of the semaphore value becoming negative. Atomicity may be achieved by using a machine instruction that can <a href="Read-modify-write" class="mw-redirect" title="Read-modify-write">read, modify, and write</a> the semaphore in a single operation. Without such a hardware instruction, an atomic operation may be synthesized by using a <a href="Mutual_exclusion#Software_solutions" title="Mutual exclusion">software mutual exclusion algorithm</a>. On <a href="Uniprocessor" class="mw-redirect" title="Uniprocessor">uniprocessor</a> systems, atomic operations can be ensured by temporarily suspending <a href="Preemption_(computing)" title="Preemption (computing)">preemption</a> or disabling hardware <a href="Interrupt" title="Interrupt">interrupts</a>. This approach does not work on multiprocessor systems where it is possible for two programs sharing a semaphore to run on different processors at the same time. To solve this problem in a multiprocessor system, a locking variable can be used to control access to the semaphore. The locking variable is manipulated using a <a href="Test-and-set" title="Test-and-set">test-and-set-lock</a> command.

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Trivial_example">Trivial example</h3></div>

<p>Consider a variable <i>A</i> and a boolean variable <i>S</i>. <i>A</i> is only accessed when <i>S</i> is marked true. Thus, <i>S</i> is a semaphore for <i>A</i>.

</p><p>One can imagine a stoplight signal (<i>S</i>) just before a train station (<i>A</i>). In this case, if the signal is green, then one can enter the train station. If it is yellow or red (or any other color), the train station cannot be accessed.

</p>

<div class="mw-heading mw-heading3"><h3 id="Login_queue">Login queue</h3></div>

<p>Consider a system that can only support ten users (S=10). Whenever a user logs in, P is called, decrementing the semaphore <i>S</i> by 1. Whenever a user logs out, V is called, incrementing <i>S</i> by 1 representing a login slot that has become available. When <i>S</i> is 0, any users wishing to log in must wait until <i>S</i> increases. The login request is enqueued onto a FIFO queue until a slot is freed. <a href="Mutual_exclusion" title="Mutual exclusion">Mutual exclusion</a> is used to ensure that requests are enqueued in order. Whenever <i>S</i> increases (login slots available), a login request is dequeued, and the user owning the request is allowed to log in. If <i>S</i> is already greater than 0, then login requests are immediately dequeued.

</p>

<div class="mw-heading mw-heading3"><h3 id="Producer–consumer_problem">Producer–consumer problem</h3></div>

<p>In the <a href="Producer%E2%80%93consumer_problem" title="Producer–consumer problem">producer–consumer problem</a>, one process (the producer) generates data items and another process (the consumer) receives and uses them. They communicate using a queue of maximum size <i>N</i> and are subject to the following conditions:

</p>

<ul><li>the consumer must wait for the producer to produce something if the queue is empty;</li>

<li>the producer must wait for the consumer to consume something if the queue is full.</li></ul>

<p>The semaphore solution to the producer–consumer problem tracks the state of the queue with two semaphores: <code>emptyCount</code>, the number of empty places in the queue, and <code>fullCount</code>, the number of elements in the queue. To maintain integrity, <code>emptyCount</code> may be lower (but never higher) than the actual number of empty places in the queue, and <code>fullCount</code> may be lower (but never higher) than the actual number of items in the queue. Empty places and items represent two kinds of resources, empty boxes and full boxes, and the semaphores <code>emptyCount</code> and <code>fullCount</code> maintain control over these resources.

</p><p>The binary semaphore <code>useQueue</code> ensures that the integrity of the state of the queue itself is not compromised, for example, by two producers attempting to add items to an empty queue simultaneously, thereby corrupting its internal state. Alternatively a <a href="Mutex" class="mw-redirect" title="Mutex">mutex</a> could be used in place of the binary semaphore.

</p><p>The <code>emptyCount</code> is initially <i>N</i>, <code>fullCount</code> is initially 0, and <code>useQueue</code> is initially 1.

</p><p>The producer does the following repeatedly:

</p>

<pre><b>produce:</b>

P(emptyCount)

P(useQueue)

putItemIntoQueue(item)

V(useQueue)

V(fullCount)

</pre>

<p>The consumer does the following repeatedly

</p>

<pre><b>consume:</b>

P(fullCount)

P(useQueue)

item ← getItemFromQueue()

V(useQueue)

V(emptyCount)

</pre>

<p>Below is a substantive example:

</p>

<ol><li>A single consumer enters its critical section. Since <code>fullCount</code> is 0, the consumer blocks.</li>

<li>Several producers enter the producer critical section. No more than <i>N</i> producers may enter their critical section due to <code>emptyCount</code> constraining their entry.</li>

<li>The producers, one at a time, gain access to the queue through <code>useQueue</code> and deposit items in the queue.</li>

<li>Once the first producer exits its critical section, <code>fullCount</code> is incremented, allowing one consumer to enter its critical section.</li></ol>

<p>Note that <code>emptyCount</code> may be much lower than the actual number of empty places in the queue, for example, where many producers have decremented it but are waiting their turn on <code>useQueue</code> before filling empty places. Note that <code>emptyCount + fullCount ≤ <i>N</i></code> always holds, with equality if and only if no producers or consumers are executing their critical sections.

</p>

<div class="mw-heading mw-heading3"><h3 id="Passing_the_baton_pattern">Passing the baton pattern</h3></div>

<p>The "Passing the baton" pattern<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> proposed by Gregory R. Andrews is a generic scheme to solve many complex concurrent programming problems in which multiple processes compete for the same resource with complex access conditions (such as satisfying specific priority criteria or avoiding starvation). Given a shared resource, the pattern requires a private "priv" semaphore (initialized to zero) for each process (or class of processes) involved and a single mutual exclusion "mutex" semaphore (initialized to one).

The pseudo-code for each process is:

</p>

<div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre><span class="kt">void</span><span class="w"> </span><span class="nf">process</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">proc_id</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">res_id</span><span class="p">)</span>

<span class="w"> </span><span class="n">resource_acquire</span><span class="p">(</span><span class="n">proc_id</span><span class="p">,</span><span class="w"> </span><span class="n">res_id</span><span class="p">);</span>

<span class="w"> </span><span class="o"><</span><span class="n">use</span><span class="w"> </span><span class="n">the</span><span class="w"> </span><span class="n">resource</span><span class="w"> </span><span class="n">res_id</span><span class="o">></span><span class="p">;</span>

<span class="w"> </span><span class="n">resource_release</span><span class="p">(</span><span class="n">proc_id</span><span class="p">,</span><span class="w"> </span><span class="n">res_id</span><span class="p">);</span>

</pre></div>

<p>The pseudo-code of the resource acquisition and release primitives are:

</p>

<div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre><span class="kt">void</span><span class="w"> </span><span class="nf">resource_acquire</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">proc_id</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">res_id</span><span class="p">)</span>

<span class="w"> </span><span class="n">P</span><span class="p">(</span><span class="n">mutex</span><span class="p">);</span>

<span class="w"> </span><span class="k">if</span><span class="p">(</span><span class="o"><</span><span class="n">the</span><span class="w"> </span><span class="n">condition</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">access</span><span class="w"> </span><span class="n">res_id</span><span class="w"> </span><span class="n">is</span><span class="w"> </span><span class="k">not</span><span class="w"> </span><span class="n">verified</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">proc_id</span><span class="o">></span><span class="p">)</span>

<span class="w"> </span><span class="o"><</span><span class="n">indicate</span><span class="w"> </span><span class="n">that</span><span class="w"> </span><span class="n">proc_id</span><span class="w"> </span><span class="n">is</span><span class="w"> </span><span class="n">suspended</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">res_id</span><span class="o">></span><span class="p">;</span>

<span class="w"> </span><span class="n">V</span><span class="p">(</span><span class="n">mutex</span><span class="p">);</span>

<span class="w"> </span><span class="o"><</span><span class="n">indicate</span><span class="w"> </span><span class="n">that</span><span class="w"> </span><span class="n">proc_id</span><span class="w"> </span><span class="n">is</span><span class="w"> </span><span class="k">not</span><span class="w"> </span><span class="n">suspended</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">res_id</span><span class="w"> </span><span class="n">anymore</span><span class="o">></span><span class="p">;</span>

<span class="w"> </span><span class="o"><</span><span class="n">indicate</span><span class="w"> </span><span class="n">that</span><span class="w"> </span><span class="n">proc_id</span><span class="w"> </span><span class="n">is</span><span class="w"> </span><span class="n">accessing</span><span class="w"> </span><span class="n">the</span><span class="w"> </span><span class="n">resource</span><span class="o">></span><span class="p">;</span>

<span class="w"> </span><span class="n">pass_the_baton</span><span class="p">();</span><span class="w"> </span><span class="c1">// See below</span>

</pre></div>

<div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre><span class="kt">void</span><span class="w"> </span><span class="nf">resource_release</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">proc_id</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">res_id</span><span class="p">)</span>

<span class="w"> </span><span class="n">P</span><span class="p">(</span><span class="n">mutex</span><span class="p">);</span>

<span class="w"> </span><span class="o"><</span><span class="n">indicate</span><span class="w"> </span><span class="n">that</span><span class="w"> </span><span class="n">proc_id</span><span class="w"> </span><span class="n">is</span><span class="w"> </span><span class="k">not</span><span class="w"> </span><span class="n">accessing</span><span class="w"> </span><span class="n">the</span><span class="w"> </span><span class="n">resource</span><span class="w"> </span><span class="n">res_id</span><span class="w"> </span><span class="n">anymore</span><span class="o">></span><span class="p">;</span>

<span class="w"> </span><span class="n">pass_the_baton</span><span class="p">();</span><span class="w"> </span><span class="c1">// See below</span>

</pre></div>

<p>Both primitives in turn use the "pass_the_baton" method, whose pseudo-code is:

</p>

<div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre><span class="kt">void</span><span class="w"> </span><span class="nf">pass_the_baton</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">res_id</span><span class="p">)</span>

<span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="o"><</span><span class="n">the</span><span class="w"> </span><span class="n">condition</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">access</span><span class="w"> </span><span class="n">res_id</span><span class="w"> </span><span class="n">is</span><span class="w"> </span><span class="nb">true</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">at</span><span class="w"> </span><span class="n">least</span><span class="w"> </span><span class="n">one</span><span class="w"> </span><span class="n">suspended</span><span class="w"> </span><span class="n">process</span><span class="o">></span>

<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="o"><</span><span class="n">choose</span><span class="w"> </span><span class="n">the</span><span class="w"> </span><span class="n">process</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">wake</span><span class="o">></span><span class="p">;</span>

<span class="w"> </span><span class="n">V</span><span class="p">(</span><span class="n">mutex</span><span class="p">);</span>

</pre></div>

<p><b>Remarks</b>

</p><p>The pattern is called "passing the baton" because a process that releases the resource as well as a freshly reactivated process will activate at most one suspended process, that is, shall "pass the baton to it". The mutex is released only when a process is going to suspend itself (resource_acquire), or when pass_the_baton is unable to reactivate another suspended process.

</p>

<div class="mw-heading mw-heading2"><h2 id="Operation_names">Operation names</h2></div>

<p>The canonical names V and P come from the initials of <a href="Dutch_language" title="Dutch language">Dutch</a> words. V is generally explained as <i>verhogen</i> ("increase"). Several explanations have been offered for P, including <i>proberen</i> ("to test" or "to try"),<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> <i>passeren</i> ("pass"), and <i>pakken</i> ("grab"). Dijkstra's earliest paper on the subject<sup id="cite_ref-ReferenceA_1-1" class="reference"><a href="#cite_note-ReferenceA-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> gives <i>passering</i> ("passing") as the meaning for <i>P</i>, and <i>vrijgave</i> ("release") as the meaning for V. It also mentions that the terminology is taken from that used in railroad signals. Dijkstra subsequently wrote that he intended <i>P</i> to stand for <i>prolaag</i>,<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> short for <i>probeer te verlagen</i>, literally "try to reduce", or to parallel the terms used in the other case, "try to decrease".<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-try-and_9-0" class="reference"><a href="#cite_note-try-and-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>

</p><p>In <a href="ALGOL_68" title="ALGOL 68">ALGOL 68</a>, the <a href="Linux_kernel" title="Linux kernel">Linux kernel</a>,<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> and in some English textbooks, the <i>V</i> and <i>P</i> operations are called, respectively, <i>up</i> and <i>down</i>. In software engineering practice, they are often called <i>signal</i> and <i>wait</i>,<sup id="cite_ref-plan9_12-0" class="reference"><a href="#cite_note-plan9-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> <i>release</i> and <i>acquire</i><sup id="cite_ref-plan9_12-1" class="reference"><a href="#cite_note-plan9-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> (standard <a href="Java_(programming_language)" title="Java (programming language)">Java</a> library),<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> or <i>post</i> and <i>pend</i>. Some texts call them <i>vacate</i> and <i>procure</i> to match the original Dutch initials.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Semaphores_vs._mutexes">Semaphores vs. mutexes</h2></div>

<p>A <a href="Mutex" class="mw-redirect" title="Mutex">mutex</a> is a <a href="Mutual_exclusion#Types_of_mutual_exclusion_devices" title="Mutual exclusion">locking mechanism</a> that sometimes uses the same basic implementation as the binary semaphore. However, they differ in how they are used. While a binary semaphore may be colloquially referred to as a mutex, a true mutex has a more specific use-case and definition, in that only the <a href="Task_(computing)" title="Task (computing)">task</a> that locked the mutex is supposed to unlock it. This constraint aims to handle some potential problems of using semaphores:

</p>

<ol><li><a href="Priority_inversion" title="Priority inversion">Priority inversion</a>: If the mutex knows who locked it and is supposed to unlock it, it is possible to promote the priority of that task whenever a higher-priority task starts waiting on the mutex.</li>

<li>Premature task termination: Mutexes may also provide deletion safety, where the task holding the mutex cannot be accidentally deleted. (This is also a cost; if the mutex can prevent a task from being reclaimed, then a garbage collector has to monitor the mutex.)</li>

<li>Termination deadlock: If a mutex-holding task terminates for any reason, the <a href="Real-time_operating_system" title="Real-time operating system">OS</a> can release the mutex and signal waiting tasks of this condition.</li>

<li>Recursion deadlock: a task is allowed to lock a <a href="Reentrant_mutex" title="Reentrant mutex">reentrant mutex</a> multiple times as it unlocks it an equal number of times.</li>

<li>Accidental release: An error is raised on the release of the mutex if the releasing task is not its owner.</li></ol>

<ul><li><a href="Async/await" title="Async/await">Async/await</a></li>

<li><a href="Flag_(programming)" title="Flag (programming)">Flag (programming)</a></li>

<li><a href="Synchronization_(computer_science)" title="Synchronization (computer science)">Synchronization (computer science)</a></li>

<li><a href="Cigarette_smokers_problem" title="Cigarette smokers problem">Cigarette smokers problem</a></li>

<li><a href="Dining_philosophers_problem" title="Dining philosophers problem">Dining philosophers problem</a></li>

<li><a href="Readers%E2%80%93writers_problem" title="Readers–writers problem">Readers–writers problem</a></li>

<li><a href="Sleeping_barber_problem" title="Sleeping barber problem">Sleeping barber problem</a></li>

<li><a href="Monitor_(synchronization)" title="Monitor (synchronization)">Monitor</a></li>

<li><a href="Spurious_wakeup" title="Spurious wakeup">Spurious wakeup</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFDijkstra" class="citation book cs1"><a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Dijkstra, Edsger W.</a> <a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD35.PDF"><i>Over de sequentialiteit van procesbeschrijvingen (EWD-35)</i></a> <span class="cs1-format">(PDF)</span>. E.W. Dijkstra Archive. Center for American History, <a href="University_of_Texas_at_Austin" title="University of Texas at Austin">University of Texas at Austin</a>.</cite> (<a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD35.html">transcription</a>) (undated, 1962 or 1963)</span>

</li>

<li id="cite_note-LittleBookOfSemaphores-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-LittleBookOfSemaphores_2-0">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://greenteapress.com/semaphores/"><i>The Little Book of Semaphores</i></a> Allen B. Downey</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFAndrews1999" class="citation book cs1">Andrews, Gregory R. (1999). <i>Foundations of Multithreaded, Parallel, and Distributed Programming</i>. Addison-Wesley.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFCarverThai2005" class="citation book cs1">Carver, Richard H.; Thai, Kuo-Chung (2005). <i>Modern Multithreading: Implementing, Testing, and Debugging Multithreaded Java and C++/Pthreads/Win32 Programs</i>. Wiley.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFMaurer2021" class="citation book cs1">Maurer, Christian (2021). <i>Nonsequential and Distributed Programming with Go</i>. Springer.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFSilberschatzGalvinGagne2008" class="citation cs2">Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008), <i>Operating System Concepts</i> (8th ed.), John Wiley & Sons. Inc, p. 234, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-470-12872-5</bdi></cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFDijkstra" class="citation book cs1"><a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Dijkstra, Edsger W.</a> <a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD74.PDF"><i>EWD-74</i></a> <span class="cs1-format">(PDF)</span>. E.W. Dijkstra Archive. Center for American History, <a href="University_of_Texas_at_Austin" title="University of Texas at Austin">University of Texas at Austin</a>.</cite> (<a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD74.html">transcription</a>)</span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFDijkstra" class="citation book cs1"><a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Dijkstra, Edsger W.</a> <a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/EWD/ewd00xx/EWD51.PDF"><i>MULTIPROGAMMERING EN DE X8 (EWD-51)</i></a> <span class="cs1-format">(PDF)</span>. E.W. Dijkstra Archive. Center for American History, <a href="University_of_Texas_at_Austin" title="University of Texas at Austin">University of Texas at Austin</a>.</cite> (<a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/EWD/transcriptions/EWD00xx/EWD51.html">transcription</a>) (in <a href="Dutch_language" title="Dutch language">Dutch</a>)</span>

</li>

<li id="cite_note-try-and-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-try-and_9-0">^</a></b></span> <span class="reference-text">Dijkstra's own translation reads "try-<i>and</i>-decrease", although that phrase might be confusing for those unaware of the <a rel="nofollow" class="external text" href="http://www.wsu.edu/~brians/errors/try.html">colloquial "try-and..."</a></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://lkml.org/lkml/2005/12/19/34">(PATCH 1/19) MUTEX: Introduce simple mutex implementation</a> Linux Kernel Mailing List, 19 December 2005</span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.linuxgrill.com/anonymous/fire/netfilter/kernel-hacking-HOWTO-5.html#ss5.3">Linux Kernel hacking HOWTO</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100528154351/http://www.linuxgrill.com/anonymous/fire/netfilter/kernel-hacking-HOWTO-5.html#ss5.3">Archived</a> 2010-05-28 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> LinuxGrill.com</span>

</li>

<li id="cite_note-plan9-12"><span class="mw-cite-backlink">^ <a href="#cite_ref-plan9_12-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-plan9_12-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFMullenderCox2008" class="citation conference cs1">Mullender, Sape; Cox, Russ (2008). <a rel="nofollow" class="external text" href="http://doc.cat-v.org/plan_9/IWP9/2008/iwp9_proceedings08.pdf#page=62"><i>Semaphores in Plan 9</i></a> <span class="cs1-format">(PDF)</span>. 3rd International Workshop on <a href="Plan_9_from_Bell_Labs" title="Plan 9 from Bell Labs">Plan 9</a>.</cite></span>

</li>

<li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/concurrent/Semaphore.html">java.util.concurrent.Semaphore</a></code></span>

</li>

<li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://amigadev.elowar.com/read/ADCD_2.1/Includes_and_Autodocs_2._guide/node036A.html">"exec.library/Procure"</a>. <i>amigadev.elowar.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2016-09-19</span></span>.</cite></span>

</li>

<li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://amigadev.elowar.com/read/ADCD_2.1/Includes_and_Autodocs_2._guide/node0389.html">"exec.library/Vacate"</a>. <i>amigadev.elowar.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2016-09-19</span></span>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Introductions">Introductions</h3></div>

<ul><li>Hilsheimer, Volker (2004). "<a rel="nofollow" class="external text" href="https://doc.qt.io/archives/qq/qq11-mutex.html">Implementing a Read/Write Mutex</a>" (Web page). <i>Qt Quarterly</i>, Issue 11 - Q3 2004</li>

<li><cite id="CITEREFZelenskiParlante" class="citation journal cs1 cs1-prop-long-vol">Zelenski, Julie; Parlante, Nick. <a rel="nofollow" class="external text" href="https://see.stanford.edu/materials/icsppcs107/23-Concurrency-Examples.pdf">"Thread and Semaphore Examples"</a> <span class="cs1-format">(PDF)</span>. <i>Handout</i>. CS107 Programming Paradigms. Spring 2008 (23). Stanford Engineering Everywhere (SEE).</cite></li></ul>

<div class="mw-heading mw-heading3"><h3 id="References_2">References</h3></div>

<ul><li><cite id="CITEREFDijkstra" class="citation book cs1"><a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Dijkstra, Edsger W.</a> <a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD123.PDF"><i>Cooperating sequential processes (EWD-123)</i></a> <span class="cs1-format">(PDF)</span>. E.W. Dijkstra Archive. Center for American History, <a href="University_of_Texas_at_Austin" title="University of Texas at Austin">University of Texas at Austin</a>.</cite> (<a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html">transcription</a>) (September 1965)</li>

<li><cite class="citation cs1">"semaphore.h - semaphores (REALTIME)". <a rel="nofollow" class="external text" href="http://www.opengroup.org/onlinepubs/009695399/basedefs/semaphore.h.html"><i>The Open Group Base Specifications Issue 6 IEEE Std 1003.1, 2004 Edition</i></a>. Open Group. 2004.</cite></li>

<li><cite id="CITEREFDowney2016" class="citation web cs1">Downey, Allen B. (2016) [2005]. <a rel="nofollow" class="external text" href="http://greenteapress.com/semaphores/">"The Little Book of Semaphores"</a> (2nd ed.). Green Tea Press.</cite></li>

<li><cite id="CITEREFLeppäjärvi2008" class="citation web cs1">Leppäjärvi, Jouni (May 11, 2008). <a rel="nofollow" class="external text" href="https://www.mv.helsinki.fi/home/joleppaj/jleppaja_gradu_080511.pdf">"A pragmatic, historically oriented survey on the universality of synchronization primitives"</a> <span class="cs1-format">(PDF)</span>. University of Oulu, Finland.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Data_types177" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Data_types177" style="font-size:114%;margin:0 4em"><a href="Data_type" title="Data type">Data types</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Units_of_information" title="Units of information">Uninterpreted</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Ternary_numeral_system#Tryte" title="Ternary numeral system">Tryte</a></li>

<li><a href="Bit_array" title="Bit array">Bit array</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Numeric</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Arbitrary-precision_arithmetic" title="Arbitrary-precision arithmetic">Arbitrary-precision or bignum</a></li>

<li><a href="Complex_data_type" title="Complex data type">Complex</a></li>

<li><a href="Decimal_data_type" title="Decimal data type">Decimal</a></li>

<li><a href="Fixed-point_arithmetic" title="Fixed-point arithmetic">Fixed point</a></li>

<li><a href="Block_floating_point" title="Block floating point">Block floating point</a></li>

<li><a href="Floating-point_arithmetic" title="Floating-point arithmetic">Floating point</a>

<ul><li>Reduced precision

<ul><li><a href="Minifloat" title="Minifloat">Minifloat</a></li>

<li><a href="Half-precision_floating-point_format" title="Half-precision floating-point format">Half precision</a></li>

<li><a href="Bfloat16_floating-point_format" title="Bfloat16 floating-point format">bfloat16</a></li></ul></li>

<li><a href="Single-precision_floating-point_format" title="Single-precision floating-point format">Single precision</a></li>

<li><a href="Double-precision_floating-point_format" title="Double-precision floating-point format">Double precision</a></li>

<li><a href="Quadruple-precision_floating-point_format" title="Quadruple-precision floating-point format">Quadruple precision</a></li>

<li><a href="Octuple-precision_floating-point_format" title="Octuple-precision floating-point format">Octuple precision</a></li>

<li><a href="Extended_precision" title="Extended precision">Extended precision</a>

<ul><li><a href="Long_double" title="Long double">Long double</a></li></ul></li></ul></li>

<li><a href="Integer_(computer_science)" title="Integer (computer science)">Integer</a>

<ul><li><a href="Signedness" title="Signedness">signedness</a></li></ul></li>

<li><a href="Interval_arithmetic#Implementations" title="Interval arithmetic">Interval</a></li>

<li><a href="Rational_data_type" title="Rational data type">Rational</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Pointer_(computer_programming)" title="Pointer (computer programming)">Pointer</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Memory_address" title="Memory address">Address</a>

<ul><li><a href="Physical_address" title="Physical address">physical</a></li>

<li><a href="Virtual_address_space" title="Virtual address space">virtual</a></li></ul></li>

<li><a href="Reference_(computer_science)" title="Reference (computer science)">Reference</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Plain_text" title="Plain text">Text</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Character_(computing)" title="Character (computing)">Character</a></li>

<li><a href="String_(computer_science)" title="String (computer science)">String</a>

<ul><li><a href="Null-terminated_string" title="Null-terminated string">null-terminated</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Composite_data_type" title="Composite data type">Composite</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Algebraic_data_type" title="Algebraic data type">Algebraic data type</a>

<ul><li><a href="Generalized_algebraic_data_type" title="Generalized algebraic data type">generalized</a></li></ul></li>

<li><a href="Array_(data_type)" title="Array (data type)">Array</a></li>

<li><a href="Associative_array" title="Associative array">Associative array</a></li>

<li><a href="Class_(computer_programming)" title="Class (computer programming)">Class</a></li>

<li><a href="Dependent_type" title="Dependent type">Dependent</a></li>

<li><a href="Intuitionistic_type_theory#Equality_type" title="Intuitionistic type theory">Equality</a></li>

<li><a href="Inductive_type" title="Inductive type">Inductive</a></li>

<li><a href="Intersection_type" title="Intersection type">Intersection</a></li>

<li><a href="Object_(computer_science)" title="Object (computer science)">Object</a>

<ul><li><a href="Metaobject" title="Metaobject">metaobject</a></li></ul></li>

<li><a href="Option_type" title="Option type">Option type</a></li>

<li><a href="Product_type" title="Product type">Product</a></li>

<li><a href="Record_(computer_science)" title="Record (computer science)">Record or Struct</a></li>

<li><a href="Refinement_type" title="Refinement type">Refinement</a></li>

<li><a href="Union_type" title="Union type">Union</a>

<ul><li><a href="Tagged_union" title="Tagged union">tagged</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Boolean_data_type" title="Boolean data type">Boolean</a></li>

<li><a href="Bottom_type" title="Bottom type">Bottom type</a></li>

<li><a href="Container_(abstract_data_type)" title="Container (abstract data type)">Collection</a></li>

<li><a href="Enumerated_type" title="Enumerated type">Enumerated type</a></li>

<li><a href="Exception_handling" title="Exception handling">Exception</a></li>

<li><a href="Function_type" title="Function type">Function type</a></li>

<li><a href="Opaque_data_type" title="Opaque data type">Opaque data type</a></li>

<li><a href="Recursive_data_type" title="Recursive data type">Recursive data type</a></li>

<li><a href="Stream_(computing)" title="Stream (computing)">Stream</a></li>

<li><a href="Strongly_typed_identifier" title="Strongly typed identifier">Strongly typed identifier</a></li>

<li><a href="Type_class" title="Type class">Type class</a></li>

<li><a href="Empty_type" title="Empty type">Empty type</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related<br>topics</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abstract_data_type" title="Abstract data type">Abstract data type</a></li>

<li><a href="Boxing_(computer_programming)" title="Boxing (computer programming)">Boxing</a></li>

<li><a href="Data_structure" title="Data structure">Data structure</a></li>

<li><a href="Generic_programming" title="Generic programming">Generic</a></li>

<ul><li><a href="Metaclass" title="Metaclass">metaclass</a></li></ul></li>

<li><a href="Parametric_polymorphism" title="Parametric polymorphism">Parametric polymorphism</a></li>

<li><a href="Primitive_data_type" title="Primitive data type">Primitive data type</a></li>

<li><a href="Interface_(object-oriented_programming)" title="Interface (object-oriented programming)">Interface</a></li>

<li><a href="Subtyping" title="Subtyping">Subtyping</a></li>

<li><a href="Type_constructor" title="Type constructor">Type constructor</a></li>

<li><a href="Type_conversion" title="Type conversion">Type conversion</a></li>

<li><a href="Type_system" title="Type system">Type system</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li>

<li><a href="Variable_(computer_science)" title="Variable (computer science)">Variable</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Software_design_patterns225" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Software_design_patterns225" style="font-size:114%;margin:0 4em"><a href="Software_design_pattern" title="Software design pattern">Software design patterns</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Design_Patterns" title="Design Patterns">Gang of Four<br>patterns</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Creational_pattern" title="Creational pattern">Creational</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abstract_factory_pattern" title="Abstract factory pattern">Abstract factory</a></li>

<li><a href="Builder_pattern" title="Builder pattern">Builder</a></li>

<li><a href="Factory_method_pattern" title="Factory method pattern">Factory method</a></li>

<li><a href="Prototype_pattern" title="Prototype pattern">Prototype</a></li>

<li><a href="Singleton_pattern" title="Singleton pattern">Singleton</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Structural_pattern" title="Structural pattern">Structural</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adapter_pattern" title="Adapter pattern">Adapter</a></li>

<li><a href="Bridge_pattern" title="Bridge pattern">Bridge</a></li>

<li><a href="Composite_pattern" title="Composite pattern">Composite</a></li>

<li><a href="Decorator_pattern" title="Decorator pattern">Decorator</a></li>

<li><a href="Facade_pattern" title="Facade pattern">Facade</a></li>

<li><a href="Flyweight_pattern" title="Flyweight pattern">Flyweight</a></li>

<li><a href="Proxy_pattern" title="Proxy pattern">Proxy</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Behavioral_pattern" title="Behavioral pattern">Behavioral</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Chain-of-responsibility_pattern" title="Chain-of-responsibility pattern">Chain of responsibility</a></li>

<li><a href="Command_pattern" title="Command pattern">Command</a></li>

<li><a href="Interpreter_pattern" title="Interpreter pattern">Interpreter</a></li>

<li><a href="Iterator_pattern" title="Iterator pattern">Iterator</a></li>

<li><a href="Mediator_pattern" title="Mediator pattern">Mediator</a></li>

<li><a href="Memento_pattern" title="Memento pattern">Memento</a></li>

<li><a href="Observer_pattern" title="Observer pattern">Observer</a></li>

<li><a href="State_pattern" title="State pattern">State</a></li>

<li><a href="Strategy_pattern" title="Strategy pattern">Strategy</a></li>

<li><a href="Template_method_pattern" title="Template method pattern">Template method</a></li>

<li><a href="Visitor_pattern" title="Visitor pattern">Visitor</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Concurrency_pattern" title="Concurrency pattern">Concurrency<br>patterns</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Active_object" title="Active object">Active object</a></li>

<li><a href="Balking_pattern" title="Balking pattern">Balking</a></li>

<li><a href="Binding_properties_pattern" title="Binding properties pattern">Binding properties</a></li>

<li><a href="Double-checked_locking" title="Double-checked locking">Double-checked locking</a></li>

<li><a href="Asynchronous_method_invocation" title="Asynchronous method invocation">Event-based asynchronous</a></li>

<li><a href="Guarded_suspension" title="Guarded suspension">Guarded suspension</a></li>

<li><a href="Monitor_(synchronization)" title="Monitor (synchronization)">Monitor</a></li>

<li><a href="Proactor_pattern" title="Proactor pattern">Proactor</a></li>

<li><a href="Reactor_pattern" title="Reactor pattern">Reactor</a></li>

<li><a href="Readers%E2%80%93writer_lock" title="Readers–writer lock">Read–write lock</a></li>

<li><a href="Scheduler_pattern" class="mw-redirect" title="Scheduler pattern">Scheduler</a></li>

<li><a href="Scheduled-task_pattern" title="Scheduled-task pattern">Scheduled-task pattern</a></li>

<li><a href="Thread_pool" title="Thread pool">Thread pool</a></li>

<li><a href="Thread-local_storage" title="Thread-local storage">Thread-local storage</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Architectural_pattern" title="Architectural pattern">Architectural<br>patterns</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Front_controller" title="Front controller">Front controller</a></li>

<li><a href="Interceptor_pattern" title="Interceptor pattern">Interceptor</a></li>

<li><a href="Specification_pattern" title="Specification pattern">Specification</a></li>

<li><a href="Publish%E2%80%93subscribe_pattern" title="Publish–subscribe pattern">Publish–subscribe</a></li>

<li><a href="Naked_objects" title="Naked objects">Naked objects</a></li>

<li><a href="Service_locator_pattern" title="Service locator pattern">Service locator</a></li>

<li><a href="Active_record_pattern" title="Active record pattern">Active record</a></li>

<li><a href="Identity_map_pattern" title="Identity map pattern">Identity map</a></li>

<li><a href="Data_access_object" title="Data access object">Data access object</a></li>

<li><a href="Data_transfer_object" title="Data transfer object">Data transfer object</a></li>

<li><a href="Inversion_of_control" title="Inversion of control">Inversion of control</a></li>

<li><a href="JSP_model_2_architecture" title="JSP model 2 architecture">Model 2</a></li>

<li><a href="Broker_pattern" title="Broker pattern">Broker</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other<br>patterns</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Blackboard_design_pattern" class="mw-redirect" title="Blackboard design pattern">Blackboard</a></li>

<li><a href="Business_delegate_pattern" title="Business delegate pattern">Business delegate</a></li>

<li><a href="Composite_entity_pattern" title="Composite entity pattern">Composite entity</a></li>

<li><a href="Dependency_injection" title="Dependency injection">Dependency injection</a></li>

<li><a href="Guard_(computer_science)" title="Guard (computer science)">Guard clause</a></li>

<li><a href="Intercepting_filter_pattern" title="Intercepting filter pattern">Intercepting filter</a></li>

<li><a href="Lazy_loading" title="Lazy loading">Lazy loading</a></li>

<li><a href="Mock_object" title="Mock object">Mock object</a></li>

<li><a href="Null_object_pattern" title="Null object pattern">Null object</a></li>

<li><a href="Object_pool_pattern" title="Object pool pattern">Object pool</a></li>

<li><a href="Servant_(design_pattern)" title="Servant (design pattern)">Servant</a></li>

<li><a href="Type_Tunnel_pattern" class="mw-redirect" title="Type Tunnel pattern">Type tunnel</a></li>

<li><a href="Method_chaining" title="Method chaining">Method chaining</a></li>

<li><a href="Delegation_pattern" title="Delegation pattern">Delegation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Books</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><i><a href="Design_Patterns" title="Design Patterns">Design Patterns</a></i></li>

<li><i><a href="Enterprise_Integration_Patterns" title="Enterprise Integration Patterns">Enterprise Integration Patterns</a></i></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">People</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Christopher_Alexander" title="Christopher Alexander">Christopher Alexander</a></li>

<li><a href="Erich_Gamma" title="Erich Gamma">Erich Gamma</a></li>

<li><a href="Ralph_Johnson_(computer_scientist)" title="Ralph Johnson (computer scientist)">Ralph Johnson</a></li>

<li><a href="John_Vlissides" title="John Vlissides">John Vlissides</a></li>

<li><a href="Grady_Booch" title="Grady Booch">Grady Booch</a></li>

<li><a href="Ward_Cunningham" title="Ward Cunningham">Ward Cunningham</a></li>

<li><a href="Martin_Fowler_(software_engineer)" title="Martin Fowler (software engineer)">Martin Fowler</a></li>

<li><a href="Robert_C._Martin" title="Robert C. Martin">Robert Martin</a></li>

<li><a href="Jim_Coplien" title="Jim Coplien">Jim Coplien</a></li>

<li><a href="Douglas_C._Schmidt" title="Douglas C. Schmidt">Douglas Schmidt</a></li>

<li><a href="Linda_Rising" title="Linda Rising">Linda Rising</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Communities</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="The_Hillside_Group" title="The Hillside Group">The Hillside Group</a></li>

<li><a href="Portland_Pattern_Repository" title="Portland Pattern Repository">Portland Pattern Repository</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">See also</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Anti-pattern" title="Anti-pattern">Anti-pattern</a></li>

<li><a href="Architectural_pattern" title="Architectural pattern">Architectural pattern</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Inter-process_communication278" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Inter-process_communication278" style="font-size:114%;margin:0 4em"><a href="Inter-process_communication" title="Inter-process communication">Inter-process communication</a></div></th></tr><tr><td class="navbox-abovebelow" colspan="2"><div><a href="Data" title="Data">Data</a> exchange among <a href="Thread_(computing)" title="Thread (computing)">threads</a> in <a href="Computer_program" title="Computer program">computer programs</a></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Methods</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Mmap" title="Mmap">Memory-mapped file</a></li>

<li><a href="Message_passing" title="Message passing">Message passing</a></li>

<li><a href="Message_queue" title="Message queue">Message queue and mailbox</a></li>

<li><a href="Named_pipe" title="Named pipe">Named pipe</a></li>

<li><a href="Anonymous_pipe" title="Anonymous pipe">Anonymous pipe</a></li>

<li><a href="Shared_memory" title="Shared memory">Shared memory</a></li>

<li><a href="Signal_(IPC)" title="Signal (IPC)">Signal</a></li>

<li>Sockets

<ul><li><a href="Network_socket" title="Network socket">Network</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Communication_protocol" title="Communication protocol">Protocols</a><br>and <a href="Technical_standard" title="Technical standard">standards</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Apple_event" title="Apple event">Apple events</a></li>

<li><a href="Common_Object_Request_Broker_Architecture" title="Common Object Request Broker Architecture">CORBA</a></li>

<li><a href="OpenBinder" title="OpenBinder">OpenBinder</a></li>

<li><a href="POSIX" title="POSIX">POSIX</a> (various methods)</li>

<li><a href="Apache_Thrift" title="Apache Thrift">Thrift</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Library_(computing)" title="Library (computing)">Software libraries</a><br>and <a href="Software_framework" title="Software framework">frameworks</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Libevent" title="Libevent">libevent</a></li>

<li><a href="SIMPL" title="SIMPL">SIMPL</a></li>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Concurrent_computing233" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Concurrent_computing233" style="font-size:114%;margin:0 4em"><a href="Concurrent_computing" title="Concurrent computing">Concurrent computing</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Concurrency_(computer_science)" title="Concurrency (computer science)">Concurrency</a></li>

<li><a href="Concurrency_control" title="Concurrency control">Concurrency control</a></li>

<li><a href="Concurrent_data_structure" title="Concurrent data structure">Concurrent data structures</a>

<ul><li><a href="Concurrent_hash_table" title="Concurrent hash table">Concurrent hash tables</a></li></ul></li>

<li><a href="Concurrent_user" title="Concurrent user">Concurrent users</a></li>

<li><a href="Indeterminacy_in_concurrent_computation" title="Indeterminacy in concurrent computation">Indeterminacy</a></li>

<li><a href="Linearizability" title="Linearizability">Linearizability</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Process_calculus" title="Process calculus">Process calculi</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Language_Of_Temporal_Ordering_Specification" class="mw-redirect" title="Language Of Temporal Ordering Specification">LOTOS</a></li>

<li><a href="%CE%A0-calculus" title="Π-calculus">π-calculus</a></li>

<li><a href="Ambient_calculus" title="Ambient calculus">Ambient calculus</a></li>

<li><a href="API-Calculus" title="API-Calculus">API-Calculus</a></li>

<li><a href="Join-calculus" title="Join-calculus">Join-calculus</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Classic problems</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="ABA_problem" title="ABA problem">ABA problem</a></li>

<li><a href="Cigarette_smokers_problem" title="Cigarette smokers problem">Cigarette smokers problem</a></li>

<li><a href="Deadlock_(computer_science)" title="Deadlock (computer science)">Deadlock</a></li>

<li><a href="Dining_philosophers_problem" title="Dining philosophers problem">Dining philosophers problem</a></li>

<li><a href="Producer%E2%80%93consumer_problem" title="Producer–consumer problem">Producer–consumer problem</a></li>

<li><a href="Race_condition" title="Race condition">Race condition</a></li>

<li><a href="Readers%E2%80%93writers_problem" title="Readers–writers problem">Readers–writers problem</a></li>

<li><a href="Sleeping_barber_problem" title="Sleeping barber problem">Sleeping barber problem</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Category: Concurrent computing</li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Parallel_computing346" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Parallel_computing346" style="font-size:114%;margin:0 4em"><a href="Parallel_computing" title="Parallel computing">Parallel computing</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Distributed_computing" title="Distributed computing">Distributed computing</a></li>

<li><a href="Parallel_computing" title="Parallel computing">Parallel computing</a></li>

<li><a href="Parallel_algorithm" title="Parallel algorithm">Parallel algorithm</a></li>

<li><a href="Massively_parallel" title="Massively parallel">Massively parallel</a></li>

<li><a href="Cloud_computing" title="Cloud computing">Cloud computing</a></li>

<li><a href="High-performance_computing" title="High-performance computing">High-performance computing</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li>

<li><a href="Manycore_processor" title="Manycore processor">Manycore processor</a></li>

<li><a href="General-purpose_computing_on_graphics_processing_units" class="mw-redirect" title="General-purpose computing on graphics processing units">GPGPU</a></li>

<li><a href="Computer_network" title="Computer network">Computer network</a></li>

<li><a href="Systolic_array" title="Systolic array">Systolic array</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Levels</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Instruction-level_parallelism" title="Instruction-level parallelism">Instruction</a></li>

<li><a href="Task_parallelism" title="Task parallelism">Thread</a></li>

<li><a href="Memory-level_parallelism" title="Memory-level parallelism">Memory</a></li>

<li><a href="Pipeline_(computing)" title="Pipeline (computing)">Pipeline</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Multithreading_(computer_architecture)" title="Multithreading (computer architecture)">Multithreading</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Temporal_multithreading" title="Temporal multithreading">Temporal</a></li>

<li><a href="Simultaneous_multithreading" title="Simultaneous multithreading">Simultaneous</a> (SMT)</li>

<li><a href="Simultaneous_and_heterogeneous_multithreading" title="Simultaneous and heterogeneous multithreading">Simultaneous and heterogenous</a></li>

<li><a href="Speculative_multithreading" title="Speculative multithreading">Speculative</a> (SpMT)</li>

<li><a href="Preemption_(computing)" title="Preemption (computing)">Preemptive</a></li>

<li><a href="Computer_multitasking#Cooperative_multitasking" title="Computer multitasking">Cooperative</a></li>

<li><a href="Bulldozer_(microarchitecture)#Bulldozer_core" title="Bulldozer (microarchitecture)">Clustered multi-thread</a> (CMT)</li>

<li><a href="Hardware_scout" title="Hardware scout">Hardware scout</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theory</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parallel_RAM" title="Parallel RAM">PRAM model</a></li>

<li><a href="Parallel_external_memory" title="Parallel external memory">PEM model</a></li>

<li><a href="Analysis_of_parallel_algorithms" title="Analysis of parallel algorithms">Analysis of parallel algorithms</a></li>

<li><a href="Amdahl's_law" title="Amdahl's law">Amdahl's law</a></li>

<li><a href="Gustafson's_law" title="Gustafson's law">Gustafson's law</a></li>

<li><a href="Cost_efficiency" title="Cost efficiency">Cost efficiency</a></li>

<li><a href="Karp%E2%80%93Flatt_metric" title="Karp–Flatt metric">Karp–Flatt metric</a></li>

<li><a href="Parallel_slowdown" title="Parallel slowdown">Slowdown</a></li>

<li><a href="Speedup" title="Speedup">Speedup</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Elements</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Process_(computing)" title="Process (computing)">Process</a></li>

<li><a href="Thread_(computing)" title="Thread (computing)">Thread</a></li>

<li><a href="Fiber_(computer_science)" title="Fiber (computer science)">Fiber</a></li>

<li><a href="Instruction_window" title="Instruction window">Instruction window</a></li>

<li><a href="Array_(data_structure)" title="Array (data structure)">Array</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Coordination</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li>

<li><a href="Memory_coherence" title="Memory coherence">Memory coherence</a></li>

<li><a href="Cache_coherence" title="Cache coherence">Cache coherence</a></li>

<li><a href="Cache_invalidation" title="Cache invalidation">Cache invalidation</a></li>

<li><a href="Barrier_(computer_science)" title="Barrier (computer science)">Barrier</a></li>

<li><a href="Synchronization_(computer_science)" title="Synchronization (computer science)">Synchronization</a></li>

<li><a href="Application_checkpointing" title="Application checkpointing">Application checkpointing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_programming" title="Computer programming">Programming</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Stream_processing" title="Stream processing">Stream processing</a></li>

<li><a href="Dataflow_programming" title="Dataflow programming">Dataflow programming</a></li>

<li><a href="Parallel_programming_model" title="Parallel programming model">Models</a>

<ul><li><a href="Implicit_parallelism" title="Implicit parallelism">Implicit parallelism</a></li>

<li><a href="Explicit_parallelism" title="Explicit parallelism">Explicit parallelism</a></li>

<li><a href="Concurrency_(computer_science)" title="Concurrency (computer science)">Concurrency</a></li></ul></li>

<li><a href="Non-blocking_algorithm" title="Non-blocking algorithm">Non-blocking algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_hardware" title="Computer hardware">Hardware</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Flynn's_taxonomy" title="Flynn's taxonomy">Flynn's taxonomy</a>

<ul><li><a href="Single_instruction%2C_multiple_threads" title="Single instruction, multiple threads">Array processing</a> (SIMT)</li>

<li><a href="Flynn's_taxonomy#Pipelined_processor" title="Flynn's taxonomy">Pipelined processing</a></li>

<li><a href="Flynn's_taxonomy#Associative_processor" title="Flynn's taxonomy">Associative processing</a></li></ul></li>

<li><a href="Dataflow_architecture" title="Dataflow architecture">Dataflow architecture</a></li>

<li><a href="Instruction_pipelining" title="Instruction pipelining">Pipelined processor</a></li>

<li><a href="Superscalar_processor" title="Superscalar processor">Superscalar processor</a></li>

<li><a href="Vector_processor" title="Vector processor">Vector processor</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessor</a>

<ul><li><a href="Symmetric_multiprocessing" title="Symmetric multiprocessing">symmetric</a></li>

<li><a href="Asymmetric_multiprocessing" title="Asymmetric multiprocessing">asymmetric</a></li></ul></li>

<li><a href="Semiconductor_memory" title="Semiconductor memory">Memory</a>

<ul><li><a href="Shared_memory" title="Shared memory">shared</a></li>

<li><a href="Distributed_memory" title="Distributed memory">distributed</a></li>

<li><a href="Distributed_shared_memory" title="Distributed shared memory">distributed shared</a></li>

<li><a href="Massively_parallel" title="Massively parallel">Massively parallel</a> computer</li>

<li><a href="Computer_cluster" title="Computer cluster">Computer cluster</a>

<ul><li><a href="Beowulf_cluster" title="Beowulf cluster">Beowulf cluster</a></li></ul></li>

<li><a href="Grid_computing" title="Grid computing">Grid computer</a></li>

<li><a href="Hardware_acceleration" title="Hardware acceleration">Hardware acceleration</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="API" title="API">APIs</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Ateji_PX" title="Ateji PX">Ateji PX</a></li>

<li><a href="Boost_(C%2B%2B_libraries)" title="Boost (C++ libraries)">Boost</a></li>

<li><a href="Chapel_(programming_language)" title="Chapel (programming language)">Chapel</a></li>

<li><a href="Charm%2B%2B" title="Charm++">Charm++</a></li>

<li><a href="Coarray_Fortran" title="Coarray Fortran">Coarray Fortran</a></li>

<li><a href="Dryad_(programming)" title="Dryad (programming)">Dryad</a></li>

<li><a href="Global_Arrays" title="Global Arrays">Global Arrays</a></li>

<li><a href="GPUOpen" title="GPUOpen">GPUOpen</a></li>

<li><a href="OpenMP" title="OpenMP">OpenMP</a></li>

<li><a href="OpenCL" title="OpenCL">OpenCL</a></li>

<li><a href="OpenHMPP" title="OpenHMPP">OpenHMPP</a></li>

<li><a href="OpenACC" title="OpenACC">OpenACC</a></li>

<li><a href="Parallel_Extensions" title="Parallel Extensions">Parallel Extensions</a></li>

<li><a href="Pthreads" title="Pthreads">pthreads</a></li>

<li><a href="RaftLib" title="RaftLib">RaftLib</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Problems</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatic_parallelization" title="Automatic parallelization">Automatic parallelization</a></li>

<li><a href="Deadlock_(computer_science)" title="Deadlock (computer science)">Deadlock</a></li>

<li><a href="Deterministic_algorithm" title="Deterministic algorithm">Deterministic algorithm</a></li>

<li><a href="Embarrassingly_parallel" title="Embarrassingly parallel">Embarrassingly parallel</a></li>

<li><a href="Parallel_slowdown" title="Parallel slowdown">Parallel slowdown</a></li>

<li><a href="Race_condition" title="Race condition">Race condition</a></li>

<li><a href="Software_lockout" title="Software lockout">Software lockout</a></li>

<li><a href="Scalability" title="Scalability">Scalability</a></li>

<li><a href="Starvation_(computer_science)" title="Starvation (computer science)">Starvation</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Category: Parallel computing</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-22" href="https://en.wikipedia.org/wiki/?title=Semaphore_(programming)&oldid=1286808798">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>